import javax.management.ListenerNotFoundException;
import java.util.*;

public class MyBinarySet {

    static class BTNode{
        int val;
        BTNode left;
        BTNode right;

        public BTNode(int val){
            this.val = val;
        }
    }

        public  BTNode root;

        public void creatNode(){

            BTNode A = new BTNode(1);
            BTNode B = new BTNode(2);
            BTNode C = new BTNode(3);
            BTNode D = new BTNode(4);
            BTNode E = new BTNode(5);
            BTNode F = new BTNode(6);
            BTNode G = new BTNode(7);
            BTNode H = new BTNode(8);

            root = A;
            A.left = B;
            A.right = C;
            B.left = D;
            B.right = E;
            C.left = F;
            C.right = G;
            D.left = H;

        }

        public void preOrder(BTNode root) {

            if (root == null) return;

            System.out.print(root.val + " ");


            preOrder(root.left);

            preOrder(root.right);
        }

    public void inOrder(BTNode root) {

        if (root == null) return;

        inOrder(root.left);

        System.out.print(root.val + " ");

        inOrder(root.right);
    }

    public void postOrder(BTNode root) {

        if (root == null) return;

        postOrder(root.left);

        postOrder(root.right);

        System.out.print(root.val + " ");
    }

    //求size
    public int size1(BTNode root){

        if(root == null) return 0;

        if(root.left == null && root.right == null) return 1;

        return size1(root.left) + size1(root.right) + 1;

    }
    int BTSize = 0;
    public void size(BTNode root){

            if(root == null) return;

            if(root.left == null && root.right == null) BTSize++;

           else{

              if(root.left != null) {

                  size(root.left);
              }
                if(root.right != null){

                    size(root.right);
                }

                BTSize++;

            }

    }

    //获取叶子节点的个数
    //int leafNodeCount = 0;
    public int leafNodeCount(BTNode root){
        if(root == null) return 0;

        if(root.left ==null && root.right == null) return 1;

        return leafNodeCount(root.left) + leafNodeCount(root.right);

    }

    //求第K层节点的个数
    public int getKLevelNodeCount(BTNode root,int k){
        if(root == null) return 0;
        if(k == 1) return 1;

        return getKLevelNodeCount(root.left,k - 1) + getKLevelNodeCount(root.right,k -1);
    }

    //获取二叉树的高度
    public int deepPath(BTNode root){

        if(root == null) return 0;

        if(root.left == null && root.right == null) return 1;

        return Math.max(deepPath(root.left) , deepPath(root.right)) + 1;
    }

    //检测二叉树中是否存在某一个节点值

    public BTNode getNode(BTNode root,int val){
        if(root == null) return null;

        if(root.val == val) return root;

        BTNode val1 = getNode(root.left,val);
        if(val1.val == val) return val1;

        BTNode val2 =getNode(root.right,val);
        if(val2.val == val) return val2;

        return null;
    }//

    //层序遍历
    public void levelOrder(BTNode root){
        if(root == null) return;

        Queue<BTNode> queue = new LinkedList<>();

        queue.offer(root);

        while (!queue.isEmpty()){
            BTNode cur = queue.poll();
            System.out.println(cur.val + " ");
            if(cur.left != null) {
                queue.offer(cur.left);
            }
            if(cur.right != null){
                queue.offer(cur.right);
            }
        }
    }

    //分层遍历
    public List<List<Integer>> levelOrder1(BTNode root) {
        if(root == null) return null;

        List<List<Integer>> ret = new LinkedList<>();

        Queue<BTNode> queue = new LinkedList<>();

        queue.offer(root);

        while (!queue.isEmpty()){
            List<Integer> cur = new LinkedList<>();

            int size = queue.size();
            while(size != 0){
               BTNode level = queue.poll();
               cur.add(level.val);
                if(root.left != null) {
                   queue.add(root.left);
                }
                if(root.right != null){
                    queue.add(root.right);
                }
                size--;
            }
           ret.add(cur);

        }
        return ret;
    }

    //判断一棵树是不是完全二叉树
    public boolean isCompleteTree(BTNode root){

        if(root == null) return false;

        if(root.left == null && root.right == null ) return true;

        //1.创建队列
       Queue<BTNode > queue = new LinkedList<>();

       queue.offer(root);

       //如果cur不为空，加入队列
       while(!queue.isEmpty()){

           BTNode cur = queue.poll();

           if(cur == null) break;

           queue.offer(cur.left);
           queue.offer(cur.right);
       }

       //如果全部是空，是完全二叉树
       int size = queue.size();
       while(size != 0){
           if(queue.peek() != null) return false;
           queue.poll();
           size--;
       }

       return true;
    }
    //求最小公共祖先：先求路劲，再求节点
        public BTNode lowestCommonAncestor(BTNode root, BTNode p, BTNode q) {

            if(root == null || root == p || root == q) return root;

            Stack<BTNode> stackP = new Stack<>();
            Stack<BTNode> stackQ = new Stack<>();

            getPath(root,p,stackP);
            getPath(root,q,stackQ);

            int sizeP = stackP.size();
            int sizeQ = stackQ.size();
            int sz = sizeP - sizeQ;

            if(sz < 0){
                sz = -sz;
                while(sz != 0){
                    stackQ.pop();
                    sz--;
                }
            }else{
                while(sz != 0){
                    stackP.pop();
                    sz--;
                }
            }

            while(!stackQ.empty() && !stackP.empty()){
                if(stackP.peek() == stackQ.peek()){
                    return stackP.peek();
                }else{
                    stackP.pop();
                    stackQ.pop();
                }
            }
            return null;

        }

        private boolean getPath(BTNode root,BTNode node, Stack stack){

            if(root == null || node == null) return false;

            stack.push(root);

            if(root == node)  return true;

            boolean flag1 = getPath(root.left,node,stack);
            if(flag1){
                return true;
            }
            boolean flag2 = getPath(root.right,node,stack);
            if(flag2){
                return true;
            }

            stack.pop();

            return false;

        }

    int postIndex = 0;
    public BTNode buildTree(int[] postorder, int[] inorder) {
        postIndex = postorder.length - 1;
        return buildTreeChild(postorder,inorder,0,inorder.length - 1);
    }

    public BTNode buildTreeChild(int[] postorder,int[] inorder,int inbegin,int inend){

        if(inbegin > inend) return null;

        BTNode root = new BTNode(postorder[postIndex]);

        int findIndex = findIndex(inorder,inbegin,inend,postorder[postIndex]);

        postIndex--;

        root.right = buildTreeChild(postorder,inorder,findIndex + 1,inend);

        root.left = buildTreeChild(postorder,inorder,inbegin, findIndex - 1);

        //root.right = buildTreeChild(postorder,inorder,findIndex + 1,inend);

        return root;

    }

    public int findIndex(int[] inorder,int inbegin,int inend,int key){

        for(int i = inbegin;i <= inend;i++){
            if(inorder[i] == key){
                return i;
            }
        }
        return -1;
    }

    public String tree2str(BTNode root) {
        StringBuilder stringBuilder = new StringBuilder();

        if(root == null) return stringBuilder.toString();

        stree2strChild(root,stringBuilder);

        return stringBuilder.toString();

    }

    private void  stree2strChild(BTNode root,StringBuilder stringBuilder){

        if(root == null) return;

        stringBuilder.append(root.val);

        if(root.left != null){
            stringBuilder.append("(");
            stree2strChild(root.left,stringBuilder);
            stringBuilder.append(")");
        }else{
            if(root.right == null){
                return;
            }
            stringBuilder.append("()");
        }

        if(root.right != null){
            stringBuilder.append("(");
            stree2strChild(root.right,stringBuilder);
            stringBuilder.append(")");
        }else{
            return;
        }
    }
    List<List<Integer>> ret = new LinkedList<>();

    public List<List<Integer>> levelOrderBottom(BTNode root) {

        List<List<Integer>> ret = new LinkedList<>();

        if(root == null) return ret;

        //创建一个栈
        Queue<BTNode> queue = new LinkedList<>();

        queue.offer(root);

        while(!queue.isEmpty()){

            List<Integer> list = new LinkedList<>();
            int size = queue.size();
            while(size != 0){
                BTNode node = queue.poll();
                list.add(node.val);
                if(node.left != null)
                queue.offer(node.left);
                if(node.right != null)
                queue.offer(node.right);
                size--;
            }
            ret.add(list);
        }

        return ret;
    }

    //非递归先序

    public List<Integer> preorderTraversal(BTNode root) {
        //创建链表
        List<Integer> list = new LinkedList<>();

//创建栈
        Stack<BTNode> stack = new Stack<>();

        if(root == null) return list;
//头节点压栈
        stack.push(root);

        while(!stack.empty()){
            //出栈
            BTNode cur = stack.pop();
            list.add(cur.val);
            //压栈：先右后左
            if(cur.right != null){
                stack.push(cur.right);
            }
            if(cur.left != null){
                stack.push(cur.left);
            }
        }

        return list;
    }

    //非递归中序：使用两层循环：先压栈左边，在压栈右边
    public List<Integer> inorderTraversal(BTNode root) {
        //1.创建一个链表和栈
        List<Integer> list = new LinkedList<Integer>();
        Stack<BTNode> stack = new Stack<>();

        //2.进入循环
        BTNode cur = root;
        while(!stack.empty() || cur != null){
            while(cur != null){
                //将左节点压栈
                stack.push(cur);
                cur = cur.left;
            }
            //此时左节点为空，栈顶为最左节点
            BTNode node = stack.pop();
            list.add(node.val);

            //判断节点右边是否还有节点
            if(node.right != null){
                cur = node.right;
            }

        }
        return list;
    }

    //非递归后续：使用两个栈，在栈1压入头节点，进入循环（不为空）,弹出栈顶
    //给栈2，在栈1加入左后加右，最后弹出栈2
    public List<Integer> postorderTraversal(BTNode root) {


        //1.创建链表与栈
        List<Integer> list = new LinkedList<>();
        if(root == null) return list;

        Stack<BTNode> stack1 = new Stack<>();
        Stack<BTNode> stack2 = new Stack<>();

        stack1.push(root);

        //2.进入循环
        while(!stack1.empty()){

            BTNode node = stack1.pop();

            stack2.push(node);

            if(node.left != null){
                stack1.push(node.left);
            }
            if(node.right != null){
                stack1.push(node.right);
            }
        }
        //3.将栈2元素弹出
        while(!stack2.empty()){

            list.add(stack2.pop().val);
        }

        return list;

    }

}
